package com.zlk.algorithm.dataStructure.tree.treeDp;

import com.zlk.algorithm.dataStructure.tree.NodeUtils;
import com.zlk.algorithm.dataStructure.tree.TreeNode;
import org.junit.Test;

import java.util.ArrayList;

/**
 * @program: algorithm
 * @ClassName IsBST
 * @description:  是否二叉搜索树
 * @author: slfang
 * @create: 2024-02-20 10:15
 * @Version 1.0
 **/
public class IsBST {


    //二叉搜索树 性质左数最大值小于父节点  右树小值大于父节点
    //可能性：
    //    1、经过 x节点
    //    2、不经过 x节点
    //信息： 最大值  最小值  isBst


    class Info{
        public int max;
        public int min;
        public boolean isBst;

        public Info(int max, int min, boolean isBst) {
            this.max = max;
            this.min = min;
            this.isBst = isBst;
        }
    }

    public boolean isBst(TreeNode node){
        if(node==null){
            return true;
        }
        return process(node).isBst;
    }

    public static boolean isBST1(TreeNode head) {
        if (head == null) {
            return true;
        }
        ArrayList<TreeNode> arr = new ArrayList<>();
        in(head, arr);
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i).value <= arr.get(i - 1).value) {
                return false;
            }
        }
        return true;
    }

    public static void in(TreeNode head, ArrayList<TreeNode> arr) {
        if (head == null) {
            return;
        }
        in(head.left, arr);
        arr.add(head);
        in(head.right, arr);
    }


    public Info process(TreeNode node){
        if(node==null){
            return null;//当不好设置的时候直接设置为空，放在后续处理
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);

        int val = node.value;
        int max = val;
        int min = val;
        boolean isBst = true;
        if(leftInfo !=null){
            if( leftInfo.max>=val){
                isBst = false;
            }

            max = Math.max(leftInfo.max,max);
            min = Math.min(leftInfo.min,min);

            if(!leftInfo.isBst){
                isBst = false;
            }
        }
        if(rightInfo !=null){
            if(rightInfo.min<=val){
                isBst = false;
            }
            max = Math.max(rightInfo.max,max);
            min = Math.min(rightInfo.min,min);
            if(!rightInfo.isBst){
                isBst = false;
            }
        }
        return new Info(max,min,isBst);
    }



    @Test
    public void test(){

        int maxLevel = 4;
        int maxValue = 100;
        int testTimes = 1000;
        for (int i = 0; i < testTimes; i++) {
            TreeNode head = NodeUtils.generateRandomBST(maxLevel, maxValue);
            if (isBST1(head) != isBst(head)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");
    }
}
